{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Plus One Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: plusOne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给单链表加一"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个用<strong>链表</strong>表示的非负整数， 然后将这个整数&nbsp;<em>再加上 1</em> 。</p>\n",
    "\n",
    "<p>这些数字的存储是这样的：最高位有效的数字位于链表的首位<meta charset=\"UTF-8\" />&nbsp;<code>head</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>head = [1,2,3]\n",
    "<strong>输出: </strong>[1,2,4]\n",
    "</pre>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>示例</strong><strong>&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>head = [0]\n",
    "<strong>输出: </strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中的节点数在<meta charset=\"UTF-8\" />&nbsp;<code>[1, 100]</code>&nbsp;的范围内。</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 9</code></li>\n",
    "\t<li>由链表表示的数字不包含前导零，除了零本身。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [plus-one-linked-list](https://leetcode.cn/problems/plus-one-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [plus-one-linked-list](https://leetcode.cn/problems/plus-one-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num=[]\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            num.append(str(p.val))\n",
    "            p=p.next\n",
    "        num=int(''.join(num))+1\n",
    "        p=head\n",
    "        last=None\n",
    "        for char in str(num):\n",
    "            if p==None:\n",
    "                p=ListNode(val=char)\n",
    "                last.next=p\n",
    "            else:\n",
    "                last=p\n",
    "                p.val=char\n",
    "                p=p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 快慢指针\n",
    "        slow = ListNode()\n",
    "        slow.next = fast = head\n",
    "        while fast:\n",
    "            if fast.val != 9:\n",
    "                slow = fast\n",
    "            fast = fast.next\n",
    "        slow.val += 1\n",
    "        cur = slow.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        return slow if slow.next == head else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                cur = head\n",
    "            head = head.next\n",
    "        \n",
    "        cur.val +=1\n",
    "        cur = cur.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        \n",
    "        if dummy.val == 0:\n",
    "            return dummy.next\n",
    "        else:\n",
    "            return dummy\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "        \n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        root = head\n",
    "        stack = []\n",
    "\n",
    "        while root:\n",
    "            stack.append(root)\n",
    "            root = root.next\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.val == 9:\n",
    "                node.val = 0\n",
    "            else:\n",
    "                node.val += 1\n",
    "                return head\n",
    "        return ListNode(1, next=head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def plusOne(self, head):\n",
    "        st = []\n",
    "        while head:\n",
    "            st.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        dummy = ListNode(0)\n",
    "        adder = 1\n",
    "        while st or adder!=0 or carry>0:\n",
    "            digit =st.pop() if st else 0\n",
    "            #print(digit,adder)\n",
    "            carry+=(digit+adder)\n",
    "            cur=ListNode(carry%10)\n",
    "            carry//=10\n",
    "            cur.next=dummy.next\n",
    "            dummy.next=cur\n",
    "            adder=0\n",
    "        return dummy.next\n",
    "        # while st or adder != 0 or carry > 0:\n",
    "        #     digit = st.pop() if st else 0\n",
    "        #     sum = digit + adder + carry\n",
    "        #     carry = 1 if sum >= 10 else 0\n",
    "        #     sum = sum - 10 if sum >= 10 else sum\n",
    "        #     cur = ListNode(sum)\n",
    "        #     cur.next = dummy.next ### 把创造好的节点往前加\n",
    "        #     dummy.next = cur\n",
    "        #     adder = 0\n",
    "        # return dummy.next\n",
    "\n",
    "# 作者：负雪明烛\n",
    "# 链接：https://leetcode.cn/problems/plus-one-linked-list/solutions/1077267/fu-xue-ming-zhu-qiu-jia-fa-xiang-xi-tu-j-rrs3/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0,head)\n",
    "        prev = dummy\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                prev = head\n",
    "            head = head.next\n",
    "        \n",
    "        prev.val += 1\n",
    "        prev = prev.next\n",
    "\n",
    "        while prev:\n",
    "            prev.val = 0\n",
    "            prev = prev.next\n",
    "        \n",
    "        return dummy if dummy.val else dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        st=[]\n",
    "        while head:\n",
    "            st.append(head.val)\n",
    "            head=head.next\n",
    "        carry=0\n",
    "        dummy=ListNode(0)\n",
    "        adder=1\n",
    "        while st or adder!=0 or carry>0:\n",
    "            digit=st.pop() if st else 0\n",
    "            sum=digit+adder+carry\n",
    "            carry=1 if sum>=10 else 0\n",
    "            sum=sum-10 if sum>=10 else sum\n",
    "            cur=ListNode(sum)\n",
    "            cur.next=dummy.next\n",
    "            dummy.next=cur\n",
    "            adder=0\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        adr = []\n",
    "        tmp = head\n",
    "        while tmp != None:\n",
    "            adr.append(tmp)\n",
    "            tmp = tmp.next\n",
    "        \n",
    "        idx = len(adr) - 1\n",
    "        while True:\n",
    "            adr[idx].val = (adr[idx].val + 1) % 10\n",
    "            if adr[idx].val != 0:\n",
    "                break\n",
    "            elif adr[idx].val == 0 and idx == 0:\n",
    "                NewHead = ListNode(1, adr[0])\n",
    "                return NewHead\n",
    "            idx -= 1\n",
    "        return head                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        c = [0]\n",
    "        \n",
    "        def backtrack(head):\n",
    "            if not head.next:\n",
    "                [c[0],head.val] = divmod((head.val+1),10)\n",
    "                return \n",
    "            backtrack(head.next)\n",
    "            [c[0],head.val] = divmod((head.val+c[0]),10)\n",
    "        backtrack(head)\n",
    "        res = ListNode()\n",
    "        if c[0]==1:\n",
    "            temp = ListNode(1)\n",
    "            temp.next = head\n",
    "            res.next = temp\n",
    "        else:\n",
    "            res.next = head\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num = 0\n",
    "        while head:\n",
    "            num = num * 10 + head.val\n",
    "            head = head.next\n",
    "        num += 1\n",
    "        lst = []\n",
    "        while num:\n",
    "            lst.append(num % 10)\n",
    "            num //= 10\n",
    "        ans = node = ListNode()\n",
    "        while lst:\n",
    "            #node.val = lst.pop()\n",
    "            node.next = ListNode(lst.pop())\n",
    "            node = node.next\n",
    "        return ans.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        def change(head):\n",
    "            pre = None\n",
    "            while head:\n",
    "                next = head.next\n",
    "                head.next = pre\n",
    "                pre = head\n",
    "                head = next\n",
    "            return pre\n",
    "        head = change(head)\n",
    "        cur = head\n",
    "        up = 1\n",
    "        while cur and cur.next:\n",
    "            up += cur.val\n",
    "            cur.val = up%10\n",
    "            up //= 10\n",
    "            cur = cur.next\n",
    "        up += cur.val\n",
    "        cur.val = up%10\n",
    "        up //= 10\n",
    "        if up:\n",
    "            cur.next = ListNode(up)\n",
    "        return change(head)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num = 0\n",
    "        while head:\n",
    "            num *= 10\n",
    "            num += head.val \n",
    "            head = head.next \n",
    "        num += 1\n",
    "        newHead = ListNode(0)\n",
    "        endnode = newHead\n",
    "        for j in str(num):\n",
    "            cur = ListNode(int(j))\n",
    "            endnode.next = cur \n",
    "            endnode = cur \n",
    "        return newHead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num=[]\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            num.append(str(p.val))\n",
    "            p=p.next\n",
    "        num=int(''.join(num))+1\n",
    "        p=head\n",
    "        last=None\n",
    "        for char in str(num):\n",
    "            if p==None:\n",
    "                p=ListNode(val=char)\n",
    "                last.next=p\n",
    "            else:\n",
    "                last=p\n",
    "                p.val=char\n",
    "                p=p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # Step 1: Reverse the linked list\n",
    "        prev = None\n",
    "        current = head\n",
    "        while current is not None:\n",
    "            next_node = current.next # 保存当天节点的下一个节点\n",
    "            current.next = prev   # 将当前节点的下一个节点指向前一个节点，实现逆序\n",
    "            prev = current       # 更新前一个节点为当前节点\n",
    "            current = next_node  # 更新当前节点为下一个节点\n",
    "        reversed_head = prev     # 逆序后的链表头部\n",
    "\n",
    "        # Step 2: Add one and handle carry\n",
    "        current = reversed_head    # 重头开始遍历逆序后的链表\n",
    "        carry = 1    # 初始化进位为1\n",
    "        prev = None  # 用于记录上一个节点\n",
    "        while current is not None:\n",
    "            current.val += carry       # 将当前节点的值加上进位\n",
    "            carry = current.val // 10  # 计算新的进位\n",
    "            current.val %= 10          # 更新当前节点的值，确保在0-9的范围内\n",
    "            if carry == 0:\n",
    "                break    # 如果没有进位，则结束循环\n",
    "            prev = current    # 更新上一个节点为当前节点\n",
    "            current = current.next  # 更新当前节点为下一个节点\n",
    "\n",
    "        if carry == 1:\n",
    "            prev.next = ListNode(1)   # 如果最高位有进位，添加一个值为1的新节点\n",
    "\n",
    "        # Step 3: Reverse the linked list back\n",
    "        prev = None\n",
    "        current = reversed_head\n",
    "        while current is not None:\n",
    "            next_node = current.next  # 保存当前节点的下一个节点\n",
    "            current.next = prev       # 将当前节点的下一个节点指向前一个节点，实现逆序(恢复原顺序)\n",
    "            prev = current            # 更新前一个节点为当前节点\n",
    "            current = next_node       # 更新当前节点为下一个节点\n",
    "\n",
    "        return prev\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "\n",
    "\n",
    "\n",
    "        def reverse(node):\n",
    "\n",
    "            dummyHead = ListNode()\n",
    "            cur = node\n",
    "            while cur:\n",
    "                next_ = cur.next\n",
    "                cur.next = dummyHead.next\n",
    "                dummyHead.next = cur\n",
    "                cur = next_\n",
    "            return dummyHead.next\n",
    "\n",
    "        reHead = reverse(head)\n",
    "        dummyHead = ListNode(-1, reHead)\n",
    "        plus = 1\n",
    "        pre = dummyHead\n",
    "        cur = reHead\n",
    "        while plus and cur:\n",
    "            next_plus = 1 if (cur.val + plus) >= 10 else 0\n",
    "            cur.val = (cur.val + plus) % 10\n",
    "            plus = next_plus\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        if plus:\n",
    "            pre.next = ListNode(1)\n",
    "        \n",
    "        return reverse(reHead)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        #哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        #找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "        \n",
    "        #最右边的非九位数加1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        #将所有9设置为0\n",
    "        while not_nine:\n",
    "            not_nine.val  = 0\n",
    "            not_nine = not_nine.next\n",
    "        \n",
    "        return sentinel if sentinel.val else sentinel.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = ListNode()\n",
    "        slow.next = head\n",
    "        while fast:\n",
    "            if fast.val != 9:\n",
    "                slow = fast\n",
    "            fast = fast.next\n",
    "        slow.val += 1\n",
    "        cur = ListNode()\n",
    "        cur = slow.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        return slow if slow.next == head else head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        \n",
    "        def backtrack(root):\n",
    "            if not root.next:\n",
    "                carry,root.val=(root.val+1)//10,(root.val+1)%10\n",
    "                return carry\n",
    "            carry=backtrack(root.next)\n",
    "\n",
    "            carry,root.val=(root.val+carry)//10,(root.val+carry)%10\n",
    "            return carry\n",
    "        carry=backtrack(head)\n",
    "        if carry:\n",
    "            t=ListNode(1)\n",
    "            t.next=head\n",
    "            head=t\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "        \n",
    "        not_nine.val += 1\n",
    "\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        special = dummy\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val != 9:\n",
    "                special = cur\n",
    "            cur = cur.next\n",
    "        special.val += 1\n",
    "        cur = special.next\n",
    "        while cur:\n",
    "            cur.val = 0\n",
    "            cur = cur.next\n",
    "        if dummy.val == 0:\n",
    "            return head\n",
    "        else:\n",
    "            return dummy\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        new_head = ListNode(0)\n",
    "        new_head.next = head\n",
    "        before_9 = None\n",
    "        cur = new_head\n",
    "        while cur.next:\n",
    "            if cur.next.val == 9:\n",
    "                if not before_9:\n",
    "                    before_9 = cur\n",
    "            else:\n",
    "                before_9 = None\n",
    "            cur = cur.next\n",
    "        if before_9:\n",
    "            before_9.val += 1\n",
    "            while before_9.next:\n",
    "                before_9 = before_9.next\n",
    "                before_9.val = 0\n",
    "        else:\n",
    "            cur.val += 1\n",
    "        return new_head if new_head.val > 0 else new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        end = head\n",
    "        carry = 0\n",
    "        stack = []\n",
    "\n",
    "        while end.next != None:\n",
    "            stack.append(end)\n",
    "            end = end.next\n",
    "        \n",
    "        # stack.append(end)\n",
    "        if end.val + 1 > 9:\n",
    "            carry = 1\n",
    "        end.val = (end.val + 1) % 10\n",
    "\n",
    "        while stack and carry > 0:\n",
    "            cur = stack.pop()\n",
    "            temp = (cur.val + carry) % 10\n",
    "            carry = (cur.val + carry) // 10\n",
    "            cur.val = temp\n",
    "        \n",
    "        if carry > 0:\n",
    "            new_head = ListNode(1)\n",
    "            new_head.next = head\n",
    "            return new_head\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        snetinel = ListNode(0)\n",
    "        snetinel.next = head\n",
    "        non_nine = snetinel \n",
    "\n",
    "        while head:\n",
    "            if head.val !=9:\n",
    "                non_nine = head \n",
    "            head = head.next\n",
    "        non_nine.val += 1\n",
    "        non_nine = non_nine.next \n",
    "\n",
    "        while non_nine:\n",
    "            non_nine.val = 0\n",
    "            non_nine = non_nine.next\n",
    "        return snetinel if snetinel.val else snetinel.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        def reverse(head):\n",
    "            if not head or (not head.next):\n",
    "                return head\n",
    "            else:\n",
    "                cur = head\n",
    "                pre = None\n",
    "                while cur:\n",
    "                    tmp = cur.next\n",
    "                    cur.next = pre\n",
    "                    pre = cur\n",
    "                    cur = tmp\n",
    "                return pre\n",
    "        cur = reverse(head)\n",
    "        head = cur\n",
    "        head.val+=1\n",
    "        while head and head.val>=10:\n",
    "            head.val-=10\n",
    "            if head.next:\n",
    "                head.next.val+=1\n",
    "            else:\n",
    "                head.next=ListNode(1)\n",
    "            head = head.next\n",
    "        return reverse(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = ListNode(0,head)\n",
    "        pre = slow\n",
    "        while fast:\n",
    "            if fast.val!=9:\n",
    "                slow = fast\n",
    "            fast=fast.next\n",
    "        slow.val+=1\n",
    "        cur = slow.next\n",
    "        while cur:\n",
    "            cur.val=0\n",
    "            cur = cur.next\n",
    "        return pre if pre.val>0 else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num=0\n",
    "        while head:\n",
    "            num*=10\n",
    "            num+=head.val\n",
    "            head=head.next\n",
    "        num+=1\n",
    "        newhead=ListNode(0)\n",
    "        endnode=newhead\n",
    "        for j in str(num):\n",
    "            cur=ListNode(int(j))\n",
    "            endnode.next=cur\n",
    "            endnode=cur\n",
    "        return newhead.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        def plus(node):\n",
    "            if not node:\n",
    "                return 1\n",
    "            \n",
    "            carry = plus(node.next)\n",
    "            ret, node.val = (node.val + carry) // 10, (node.val + carry) % 10\n",
    "            return ret\n",
    "        \n",
    "        carry = plus(head)\n",
    "        if carry:\n",
    "            return ListNode(1, head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        if sentinel.val:\n",
    "            return sentinel\n",
    "        else:\n",
    "            return sentinel.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        reversed_head = self.reverseLL(head)\n",
    "        cur = reversed_head\n",
    "        while cur:\n",
    "            if cur.val == 9:\n",
    "                cur.val = 0\n",
    "                if not cur.next:\n",
    "                    cur.next = ListNode(1)\n",
    "                    break\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur.val += 1\n",
    "                break\n",
    "        reversed_reversed_head = self.reverseLL(reversed_head)\n",
    "        return reversed_reversed_head\n",
    "        \n",
    "    \n",
    "    def reverseLL(self, head):\n",
    "        if not head.next:\n",
    "            return head\n",
    "        cur = head\n",
    "        new_head = head.next\n",
    "        cur.next = None\n",
    "        while new_head:\n",
    "            tmp = new_head\n",
    "            new_head = new_head.next\n",
    "            tmp.next = cur\n",
    "            cur = tmp\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        num = 0\n",
    "        p = head\n",
    "\n",
    "        i = 1\n",
    "        while p:\n",
    "            num = num*10+p.val\n",
    "            i *=10\n",
    "            p = p.next\n",
    "\n",
    "        num +=1\n",
    "\n",
    "        p = head\n",
    "        num = (str(num))\n",
    "        pre = None\n",
    "        while p:\n",
    "            p.val = int(num[0])\n",
    "            num = num[1:]\n",
    "            pre = p\n",
    "            p = p.next\n",
    "\n",
    "        if len(num) > 0:\n",
    "            pre.next = ListNode(val=int(num[0]))\n",
    "\n",
    "        return head\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        \n",
    "        notNine = sentinel\n",
    "\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                notNine = head\n",
    "            head = head.next\n",
    "        \n",
    "        notNine.val += 1\n",
    "        notNine = notNine.next\n",
    "        while notNine:\n",
    "            notNine.val = 0\n",
    "            notNine = notNine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        L = []\n",
    "        while head:\n",
    "            L.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        n = len(L)\n",
    "        L[-1] += 1\n",
    "        for i in range(len(L) - 1, -1, -1):\n",
    "            L[i] += carry\n",
    "            if L[i] > 9:\n",
    "                L[i] -= 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "        if carry:\n",
    "            L = [1] + L \n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        for i in L:\n",
    "            cur.next = ListNode(i)\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        if not head.next:\n",
    "            #length=1\n",
    "            if head.val<9:\n",
    "                head.val+=1\n",
    "                return head\n",
    "            else:\n",
    "                pre=ListNode(1,head)\n",
    "                head.val=0\n",
    "                return pre\n",
    "\n",
    "        def reverseList(input_head):\n",
    "            pre, cur= None, input_head\n",
    "            while cur:\n",
    "                temp=cur.next\n",
    "                cur.next,pre,cur = pre, cur, temp\n",
    "            return pre\n",
    "        \n",
    "        cur=reverseList(head)\n",
    "        print(\"cur:\", cur)\n",
    "        dummy=ListNode(-1,cur)\n",
    "        cur=dummy.next\n",
    "        cur.val+=1\n",
    "        while cur:\n",
    "            if cur.val<=9:\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                cur.val=0\n",
    "                if cur.next:\n",
    "                    cur.next.val+=1\n",
    "                    cur=cur.next\n",
    "                else:\n",
    "                    newHead = ListNode(1,None)\n",
    "                    cur.next=newHead\n",
    "                    # break\n",
    "        \n",
    "        # print(\"dummy:\", dummy)\n",
    "        # res=reverseList(dummy.next)\n",
    "        # print(res)\n",
    "        return reverseList(dummy.next)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        # 哨兵头节点\n",
    "        sentinel = ListNode(0)\n",
    "        sentinel.next = head\n",
    "        not_nine = sentinel\n",
    "\n",
    "        # 找出最右边的非九位数\n",
    "        while head:\n",
    "            if head.val != 9:\n",
    "                not_nine = head\n",
    "            head = head.next\n",
    "\n",
    "        # 最右边的非九位数加 1\n",
    "        not_nine.val += 1\n",
    "        not_nine = not_nine.next\n",
    "\n",
    "        # 将所有 9 设置为 0\n",
    "        while not_nine:\n",
    "            not_nine.val = 0\n",
    "            not_nine = not_nine.next\n",
    "\n",
    "        return sentinel if sentinel.val else sentinel.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        def pohook(head: ListNode) -> bool:\n",
    "            if not head:\n",
    "                return True\n",
    "            head.val += pohook(head.next)\n",
    "            res = head.val//10\n",
    "            head.val%=10\n",
    "            return res\n",
    "        res = pohook(head)\n",
    "        if res:\n",
    "            new_head = ListNode(1,head)\n",
    "            return new_head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        rev = None\n",
    "        while head.next:\n",
    "            rev, head.next, head = head, rev, head.next\n",
    "        c, head.val = divmod(head.val + 1, 10)\n",
    "        while rev:\n",
    "            c, rev.val = divmod(rev.val + c, 10)\n",
    "            head, rev.next, rev = rev, head, rev.next\n",
    "        return ListNode(1, head) if c else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def plusOne(self, head):\n",
    "        st = []\n",
    "        while head:\n",
    "            st.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        dummy = ListNode(0)\n",
    "        adder = 1\n",
    "        while st or adder != 0 or carry > 0:\n",
    "            digit = st.pop() if st else 0\n",
    "            sum = digit + adder + carry\n",
    "            carry = 1 if sum >= 10 else 0\n",
    "            sum = sum - 10 if sum >= 10 else sum\n",
    "            cur = ListNode(sum)\n",
    "            cur.next = dummy.next\n",
    "            dummy.next = cur\n",
    "            adder = 0\n",
    "        return dummy.next\n",
    "\n",
    "# 作者：负雪明烛\n",
    "# 链接：https://leetcode.cn/problems/plus-one-linked-list/solutions/1077267/fu-xue-ming-zhu-qiu-jia-fa-xiang-xi-tu-j-rrs3/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "      node = head\n",
    "      if head.val == 9:\n",
    "        while node.next != None and node.next.val == 9:\n",
    "          node = node.next\n",
    "        if node.next == None:\n",
    "          head = ListNode(1, head)\n",
    "          node = head.next\n",
    "          while node != None:\n",
    "            node.val = 0\n",
    "            node = node.next\n",
    "          return head\n",
    "\n",
    "      \n",
    "      while node.next != None:\n",
    "        prev9 = node\n",
    "        while node.next != None and node.next.val == 9:\n",
    "          node = node.next\n",
    "        if node.next == None:\n",
    "          prev9.val += 1\n",
    "          node = prev9.next\n",
    "          while node != None:\n",
    "            node.val = 0\n",
    "            node = node.next\n",
    "          return head\n",
    "        else:\n",
    "          node = node.next\n",
    "      node.val += 1\n",
    "      return head\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        stack = []\n",
    "        while head:\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "        carry = 0\n",
    "        add = 1\n",
    "        dummy = ListNode(0)\n",
    "        while stack or add != 0 or carry != 0:\n",
    "            tmp = stack.pop() if stack else 0\n",
    "            sums = tmp + add + carry\n",
    "            carry = 1 if sums >= 10 else 0\n",
    "            sums = sums - 10 if sums >= 10 else sums\n",
    "            node = ListNode(sums)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "            add = 0\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "        p = head\n",
    "        num = []\n",
    "        while p:\n",
    "            num.append(p.val)\n",
    "            p = p.next\n",
    "        n = len(num)\n",
    "        stop = n-1\n",
    "        while stop > -1 and num[stop] == 9:\n",
    "            stop -= 1\n",
    "        if stop == -1:\n",
    "            p = head\n",
    "            head = ListNode(1)\n",
    "            head.next = p\n",
    "            while p:\n",
    "                p.val = 0\n",
    "                p = p.next\n",
    "        else:\n",
    "            cur = 0\n",
    "            p = head\n",
    "            while p:\n",
    "                if cur == stop:\n",
    "                    p.val += 1\n",
    "                if cur > stop:\n",
    "                    p.val = 0\n",
    "                p = p.next\n",
    "                cur += 1\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def plusOne(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        \n",
    "        def backtrack(root):\n",
    "            if not root.next:\n",
    "                carry,root.val=(root.val+1)//10,(root.val+1)%10\n",
    "                return carry\n",
    "            carry=backtrack(root.next)\n",
    "\n",
    "            carry,root.val=(root.val+carry)//10,(root.val+carry)%10\n",
    "            return carry\n",
    "        carry=backtrack(head)\n",
    "        if carry:\n",
    "            t=ListNode(1)\n",
    "            t.next=head\n",
    "            head=t\n",
    "        return head\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
